Show the code
using Combinatorics
2024年6月29日 #30 日曜数学会




全部で何通りありのか?→今回もJulia言語を用いて調べてみます!
何も考えずに,0と1の成分の正方行列を作ると,約687億個の行列をチェックしなくてはなりません。これを調べるのはこれは厳しいです。だいたい,億を超えると厳しいです。
\[2^{36}=68,719,476,736\]
36個の成分で0と1が半分ずつ(18個ずつ)です。これで絞ってみます。約90億個となりました。少し減りましたが,億を超えてますね。
\[{}_{36}\text{C}_{18}=9,075,135,300\]
今回の分け方「2つの合同な図形」を考えると,行列の成分は点対称になります。なので,半分の18個の成分を決めれば,あとは定まります。約26万個となり,これなら計算できそうです!
\[2^{18}=262,144\]
さらに,[1,1]成分を1に限定すれば,半分の約13万個となります。
\[\dfrac{262,144}{2} = 131,072\]
Combinatorics.jlを読み込みusing CombinatoricsA = [0,1]2-element Vector{Int64}:
0
1
B =[]
for x ∈ A , y ∈ A, z ∈ A, u ∈ A, v ∈ A, w ∈ A
push!(B,[x,y,z,u,v,w])
end
B64-element Vector{Any}:
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 1]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 1, 0, 1]
[0, 0, 0, 1, 1, 0]
[0, 0, 0, 1, 1, 1]
[0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 1]
[0, 0, 1, 0, 1, 0]
[0, 0, 1, 0, 1, 1]
[0, 0, 1, 1, 0, 0]
⋮
[1, 1, 0, 1, 0, 0]
[1, 1, 0, 1, 0, 1]
[1, 1, 0, 1, 1, 0]
[1, 1, 0, 1, 1, 1]
[1, 1, 1, 0, 0, 0]
[1, 1, 1, 0, 0, 1]
[1, 1, 1, 0, 1, 0]
[1, 1, 1, 0, 1, 1]
[1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 1]
C =[]
for x ∈ B , y ∈ B, z ∈ B
X = [x y z ]
if X[1,1] == 1
Y = mod.(X .+1,2) |> rot180
push!(C,[X Y])
end
end
C131072-element Vector{Any}:
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
[1 0 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 1 0]
⋮
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
C[5000]6×6 Matrix{Int64}:
1 0 0 0 1 0
0 0 0 0 0 1
0 1 0 0 0 1
0 1 1 1 0 1
0 1 1 1 1 1
1 0 1 1 1 0
このあとは,2つの合同な図形に分かれるということは,[1,1]の成分1から,1である18個の成分すべてが連結していなくてなりません。これをチェックすることにします。
conti_18を作成function conti_18(A::Matrix) #6x6の行列を入力 各成分は0,1
k = A[1,1] # [1,1]成分
Pack = [[1,1]] #連結する成分を加えていく
t = 1 # パラメータ
x = 18 # パラメータ
while t != x
for i = 1:6,j=1:6
if A[i,j] == k
if [i-1,j] in Pack ||[i+1,j] in Pack ||[i,j-1] in Pack ||[i,j+1] in Pack
push!(Pack,[i,j])
end
end
end
x = t
t = Pack |> union |>length
end
P = Pack |> union
endconti_18 (generic function with 1 method)
D = []
for X in C
if conti_18(X) |> length == 18
push!(D,X)
end
end
D1018-element Vector{Any}:
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
[1 1 … 1 1; 0 0 … 1 1; … ; 0 0 … 1 1; 0 0 … 0 0]
⋮
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
だいぶん減りましたね。1018個です。
D[500]6×6 Matrix{Int64}:
1 1 1 1 1 1
1 1 0 0 0 0
1 1 0 0 0 0
1 1 1 1 0 0
1 1 1 1 0 0
0 0 0 0 0 0
1,018個を見たところ,90度回転や折り返しで重なるものがあったのでそれらを除きます。(Dを置き直し)
X =[]
for i = 1:length(D)-1 , j = i+1:length(D)
if D[i] == rotr90(D[j]) #右90度回転
push!(X,D[i])
elseif D[i] == rotl90(D[j]) #左90度回転
push!(X,D[i])
elseif D[i] == rotl90(D[j]') #左右折り返し
push!(X,D[i])
end
end
D = setdiff(D,X)255-element Vector{Any}:
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
[1 1 … 1 0; 1 0 … 1 0; … ; 1 0 … 1 0; 1 0 … 0 0]
⋮
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
[1 1 … 0 0; 1 1 … 0 0; … ; 1 1 … 0 0; 1 1 … 0 0]
255通りです。これで,重複はなさそうです!
Plots.jlを読み込みusing Plotsrect_numberを作る。function rect_number(x::Int,y::Int)
xval = [x-1,x,x,x-1,x-1]
yval = [y-1,y-1,y,y,y-1]
return xval,yval
endrect_number (generic function with 1 method)
draw_rectを作る。#
function draw_rect(A::Matrix , n=6 , k=0)
plot(label=false,xlim=(0,n),ylim=(0,n),aspectratio=true,showaxis=false,framestyle=:box,ticks=0:1:n)
for i = 1:n ,j = 1:n
if mod(A[i,j],2) == 0
plot!(rect_number(i,j),fill=true,color=:royalblue,label=false,alpha=.5)
else
plot!(rect_number(i,j),fill=true,color=:Brown3,label=false,alpha=.5)
end
end
plot!(title = k)
enddraw_rect (generic function with 3 methods)
plt = []
for i =1:50
push!(plt, draw_rect(D[i],6,i))
end
plot(plt...,layout=(10,5),size=(800,2400))plt = []
for i =51:100
push!(plt, draw_rect(D[i],6,i))
end
plot(plt...,layout=(10,5),size=(800,2400))plt = []
for i =101:150
push!(plt, draw_rect(D[i],6,i))
end
plot(plt...,layout=(10,5),size=(800,2400))plt = []
for i =151:200
push!(plt, draw_rect(D[i],6,i))
end
plot(plt...,layout=(10,5),size=(800,2400))plt = []
for i =201:255
push!(plt, draw_rect(D[i],6,i))
end
plot(plt...,layout=(11,5),size=(800,2400))